package algorithm.graph;

import algorithm.linear.SeqList;

/**
 * 邻接矩阵表示的图类，实现图接口
 * @param <E>
 */
public class AdjMatrixGraph<E> implements  GGraph<E> {
    //顺序表存储图的顶点集合
    protected SeqList<E> vertexlist;
    //图的邻接矩阵
    protected int[][] adjmatrix;
    //最大权值（表示无穷大）
    private final int MAX_WEIGHT = Integer.MAX_VALUE;

    //n指定最多顶点数
    public AdjMatrixGraph(int n){
        this.vertexlist = new SeqList<E>(n);//指定容量的空顺序表
        this.adjmatrix = new int[n][n];//构造N行n列的空矩阵
        //初始化图
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                this.adjmatrix[i][j] = (i==j)?0:MAX_WEIGHT;//边的权值为0或最大权值
        }
    }

    //以顶点集合和边集合构造一个图
    public AdjMatrixGraph(E[] vertices, Edge[] edges){
        this(vertices.length);
        for(int i=0;i<vertices.length;i++)
            insertVertex(vertices[i]);//插入一个顶点
        for(int j=0;j<edges.length;j++)
            insertEdge(edges[j]);//插入一条边
    }

    //返回顶点数
    public int vertexCount() {
        return this.vertexlist.length();
    }
    //返回顶点i数据的元素
    public E get(int i) {
        return this.vertexlist.get(i);
    }
    //插入一个顶点
    public boolean insertVertex(E vertex) {
        return this.vertexlist.add(vertex);
    }
    //插入一条权值为weight的边
    public boolean insertEdge(int i, int j, int weight) {
        if(i>=0 && i<vertexCount() && j>=0 && j<vertexCount() && i!=j && adjmatrix[i][j] == MAX_WEIGHT){
            this.adjmatrix[i][j] = weight;
            return true;
        }
        return false;
    }
    //插入一条边
    public boolean insertEdge(Edge edge) {
        if(edge!=null)
            return insertEdge(edge.start,edge.dest,edge.weight);
        return false;
    }
    //删除顶点及其关联的边
    public boolean removerVertex(int v) {
        int n = vertexCount();
        if(v>=0 && v<n){
            this.vertexlist.remove(v);
            for(int i=v;i<n-1;i++){
                for(int j=0;j<n;j++) {
                    this.adjmatrix[i][j] = this.adjmatrix[i+1][j];//元素向前移一行
                }
            }
            for(int j=v;j<n-1;j++)
                for(int i=0;i<n-1;i++)
                    this.adjmatrix[i][j] = this.adjmatrix[i][j+1];//向前移一列
            return true;
        }
        return false;
    }
    //删除边
    public boolean removeEdge(int i, int j) {
        if(i>=0 && i<vertexCount() && j>=0 && j<vertexCount() && i!=j && adjmatrix[i][j] != MAX_WEIGHT){
                this.adjmatrix[i][j] = MAX_WEIGHT;
            return true;
        }
        return false;
    }
    //返回顶点v的第一个邻接顶点的序号
    public int getFirstNeighbor(int v) {
        return getNextNeighbor(v,-1);
    }
    //返回v再w后的下一个邻接顶点的序号
    public int getNextNeighbor(int v, int w) {
        if(v>=0 && v<vertexCount() && w>=-1 && w<vertexCount() && v!=w)
            for(int j=w+1;j<vertexCount();j++) //w=-1时，j从0开始寻找下一个邻接顶点
                if(adjmatrix[v][j]>0 &&adjmatrix[v][j]<MAX_WEIGHT)
                    return j;
        return -1;
    }
    //获取图的顶点集合和邻接矩阵
    public String toString() {
        String str = "顶点集合:"+vertexlist.toString()+"\n";
        str += "邻接矩阵：\n";
        int n = vertexCount();

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++) {
                if (adjmatrix[i][j] == MAX_WEIGHT) //边的权值为0或最大权值
                    str += " 无穷";
                else
                    str += " " + adjmatrix[i][j];

            }
            str += "\n";
        }
        return str;
    }
}
